package Algorithms.classic;

/**
 * 项目名称：test<br/>
 * *********************************<br/>
 * <p>类名称：TestSort</p>
 * *********************************<br/>
 * <p>类描述：各种排序算法测试：插入，希尔，选择，冒泡，快排，归并排序</p>
 * 创建人：zhouzhihui<br/>
 * 创建时间：2017/3/6 16:10<br/>
 * 修改人：周志辉<br/>
 * 修改时间：2017/3/6 16:10<br/>
 * 修改备注：<br/>
 *
 * @version 1.0<br />
 */
public class TestSort {
    /**
     * 插入排序
     *
     * @param array
     * @return
     */
    public static int[] insertSort(int[] array) {
        int temp, j;
        for (int i = 1; i < array.length; i++) {
            temp = array[i];
            j = i - 1;
            while (j >= 0 && array[j] > temp) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = temp;
        }
        return array;
    }


    /**
     * 希尔排序
     * 插入排序的改进
     * 原版是以2分步长实现的，但是实际性能不高，最差情形下会退化到插入排序的效率
     * 这是因为步长最好取互质的数，以达到最好的排序性能，而二分步长，一般不符合这一原则
     * @param array
     * @return
     */
    public static int[] shellSort(int[] array) {
       int temp, j;
       int step = 1;
       while(step <= array.length /3) {
           step = step * 3 + 1;
       }
       while(step > 0) {
           for (int i = step; i < array.length; i++) {
               temp = array[i];
               j = i;
               while(j > step - 1 && array[j - step] > temp) {
                   array[j] = array[j - step];
                   j -= step;
               }
               array[j] = temp;
           }

           step = (step - 1) / 3;
       }
        return array;
    }


    /**
     * 冒泡排序
     *
     * @param array
     * @return
     */
    public static int[] bubbleSort(int[] array) {
        int temp;
        //外层从左边往右移
        for (int i = 0; i < array.length; i++) {
            //内层从右往左移，每次把最大或最小的，移到最左侧，这样外层当前序号前面的都是那次循环里最大或最小的
            for (int j = array.length - 1; j > 0; j--) {
                if (array[j - 1] > array[j]) {
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }



    /**
     * <p>方法描述: 快排</p>
     *
     * <p>方法备注: 快排是对冒泡排序的改进</p>
     *
     * @param array 数组
     * @return 排序后的数组
     * <p>创建人：周志辉</p>
     * <p>创建时间：2017/3/27 16:30</p>
     */
    public static int[] quickSort(int[] array) {
        return quickSort(array, 0, array.length - 1);
    }


    private static int[] quickSort(int[] array, int start, int end) {
        if (end <= start) {
            return array;
        }
        int i = start;
        int j = end;
        int flag = array[start];
        int temp;
        do {
            while (i < j && array[j] >= flag) {
                j--;
            }
            while (i < j && array[i] <= flag) {
                i++;
            }
            if (i < j) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        } while (i < j);
        array[start] = array[j];
        array[j] = flag;
        quickSort(array, start, j - 1);
        quickSort(array, j + 1, end);
        return array;
    }


    /**
     * 选择排序
     *
     * @param array
     * @return
     */
    public static int[] selectSort(int[] array) {
        int temp, minIndex;
        for (int i = 0; i < array.length; i++) {
            minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
        return array;
    }


    public static int[]  mergeSort(int[] array) {
        int[] temp = new int[array.length];
         mergeSort(array, temp, 0, array.length - 1);
         return array;
    }

    private static void mergeSort(int[] array, int[] temp, int low, int high) {
        if(low == high) {
            return;
        }
        int mid = (low +  high) / 2;
        mergeSort(array, temp, low, mid);
        mergeSort(array,  temp, mid + 1, high);
        merge(array, temp, low, mid + 1, high);
    }

    private static void merge(int[] array, int[] temp, int low, int mid, int high) {
        int index = low;
        int lowIndex = low;
        int highIndex = mid;
        while(lowIndex < mid && highIndex <= high) {
            if(array[lowIndex] > array[highIndex]) {
                temp[index++] = array[highIndex++];
            } else {
                temp[index++] = array[lowIndex++];
            }
        }
        if(lowIndex == mid) {
            while(highIndex <= high) {
                temp[index++] = array[highIndex++];
            }
        } else {
            while(lowIndex < mid) {
                temp[index++] = array[lowIndex++];
            }
        }

        for (int i = low; i <= high; i++) {
            array[i] = temp[i];
        }
    }

    public static void test() {
        int[] array;
        int[] tempArray;
        for (int i = 0; i < 10; i++) {
            array = SortUtils.createRandomArray(100000, 100000000);
            tempArray = array.clone();
            long start = System.currentTimeMillis();
            System.out.print(SortUtils.isSorted(sort(array)));
            System.out.print("\t\tduration1 : " + (System.currentTimeMillis() - start) + "\t\t\t\t");

            start = System.currentTimeMillis();
            System.out.print(SortUtils.isSorted(quickSort(tempArray, 0, array.length - 1)));
            System.out.println("\t\tduration2 : " + (System.currentTimeMillis() - start));
//            System.out.println(isSorted(quickSort(array, 0, array.length - 1)));
        }
    }


    public static void testPerformance() {
        int[] array;
        for (int i = 0; i < 10; i++) {
            //100_000, 100_000_000，快排9-22ms和希尔大概在16-46ms，直接插入在1300ms，冒泡排序在15-18s，
            array = SortUtils.createRandomArray(100_000, 100_000_000);
            long start = System.currentTimeMillis();
            System.out.print(SortUtils.isSorted(sort(array)));
            System.out.println("\t\tduration1 : " + (System.currentTimeMillis() - start) + "\t\t\t\t");
        }
    }


    public static int[] test(int[] unsorted) {
        int temp;
        for (int i = 0; i < unsorted.length; i++) {
            for (int j = i; j < unsorted.length; j++) {
                if (unsorted[i] > unsorted[j]) {
                    temp = unsorted[i];
                    unsorted[i] = unsorted[j];
                    unsorted[j] = temp;
                }
            }
        }
        return unsorted;
    }


    public static int[] sort(int[] array) {
        //冒泡1
        //for (int out = 0; out < array.length - 1; out++) {
        //    for (int in = array.length - 1; in > out; in--) {
        //        if(array[in] < array[in - 1]) {
        //            swap(array, in - 1, in);
        //        }
        //    }
        //}

        //选择排序
        //int minIndex;
        //for (int out = 0; out < array.length - 1; out++) {
        //    minIndex = out;
        //    for (int in = out + 1; in < array.length; in++) {
        //        if(array[in] < array[minIndex]) {
        //            minIndex = in;
        //        }
        //    }
        //    swap(array, out, minIndex);
        //}

        //插入排序
        //int current;
        //for (int out = 1; out < array.length; out++) {
        //    current = array[out];
        //    int in = out;
        //    while(in > 0 && current < array[in - 1]) {
        //        array[in] = array[in - 1];
        //        in--;
        //    }
        //    array[in] = current;
        //}

        //希尔
        //int current, in;
        //int step = 1;
        //while(step < array.length / 3) {
        //    step = step * 3 + 1;
        //}
        //while(step > 0) {
        //    for (int out = step; out < array.length; out++) {
        //        current = array[out];
        //        in = out;
        //        while(in > step - 1 && current < array[in - step]) {
        //            array[in] = array[in - step];
        //            in -= step;
        //        }
        //        array[in] = current;
        //    }
        //    step = (step - 1) / 3;
        //}

        //鸡尾酒排序
        //boolean flag = false;
        //int current, tail, head, i, j;
        //tail = array.length - 1;
        //head = 0;
        //while(head < tail) {
        //    j = tail;
        //    for (i = head; i < j; i++) {
        //        if(array[i] > array[i + 1]) {
        //            current = array[i + 1];
        //            array[i + 1] = array[i];
        //            array[i] = current;
        //            tail = i;
        //            flag = true;
        //        }
        //    }
        //    j = head;
        //    for (i = tail; i > j; i--) {
        //        if(array[i - 1] > array[i]) {
        //            current = array[i - 1];
        //            array[i - 1] = array[i];
        //            array[i] = current;
        //            head = i;
        //        }
        //    }
        //    if(flag) {
        //        break;
        //    }
        //}

        //int head, tail, current, j;
        //boolean flag = true;
        //head = 0;
        //tail = array.length - 1;
        //while(flag)
        //{
        //    j = tail;
        //    flag = false;
        //    for(int i = head; i < j; i++)
        //    {
        //        if(array[i] > array[i + 1])
        //        {
        //            current = array[i];
        //            array[i] = array[i + 1];
        //            array[i + 1] = current;
        //            tail = i;
        //            flag = true;
        //        }
        //    }
        //}
        return array;
    }


    /**
     * 交换算法
     * @param array
     * @param index1
     * @param index2
     */
    public static void swap(int[] array, int index1, int index2) {
        //中间变量法
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;

        //求和(差)法,可能溢出，但不影响结果,改用相乘相除，则在溢出情况下，则结果不对
//        array[index1] = array[index1] * array[index2];
//        array[index2] = array[index1] / array[index2];
//        array[index1] = array[index1] / array[index2];

        //位运算,一旦出现index1==index2,则执行有问题
//        if(index1 == index2) {
//            return;
//        }
//        array[index1] = array[index1] ^ array[index2];
//        array[index2] = array[index1] ^ array[index2];
//        array[index1] = array[index1] ^ array[index2];
    }


    public static void main(String[] args) throws NoSuchMethodException {
        SortUtils.test(TestSort::
//                mergeSort
//                quickSort
//                shellSort
                sort
        );
//        int[] array = {1,3};
//        array[0] = array[0] ^ array[1];
//        array[1] = array[0] ^ array[1];
//        array[0] = array[0] ^ array[1];
//        System.out.println(Arrays.toString(array));
    }
}
